package com.le.enhance.class1;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给定两颗二叉树,判断tree1是否包含tree2
 * 思路:
 * 1. 序列化树
 * 2. kmp
 */
public class Code_02_TreeKmp {
    public static class Node {
        int data;
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
        }
    }

    /**
     * 二叉树先序序列化
     * @param head
     * @return
     */
    public static String serialize(Node head) {
        if (head == null) {
            return "#!";
        }
        String res = head.data + "!";
        res += serialize(head.left);
        res += serialize(head.right);
        return res;
    }

    /**
     * 反序列化
     * @param preStr
     * @return
     */
    public static Node reconByPreString(String preStr) {
        String[] strs = preStr.split("!");
        Queue<String> queue = new LinkedList<>();
        for (int i = 0; i < strs.length; i++) {
            queue.offer(strs[i]);
        }
        return reconsPreOrder(queue);
    }

    /**
     * 重构二叉树
     * @param queue
     * @return
     */
    public static Node reconsPreOrder(Queue<String> queue) {
        String val = queue.poll();
        if ("#".equals(val)) {
            return null;
        }
        Node head = new Node(Integer.valueOf(val));
        head.left = reconsPreOrder(queue);
        head.right = reconsPreOrder(queue);
        return head;
    }

    public static void printTree(Node head) {
        if (head == null) {
            return;
        }
        System.out.print(head.data + "   ");
        printTree(head.left);
        printTree(head.right);
    }

    public static int[] getNextArray(char[] str) {
        if (str.length == 2) {
            return new int[]{-1, 0};
        }
        int[] next = new int[str.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < next.length) {

            if (str[i - 1] == str[cn]) {
                i++;
                cn++;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }

    public static boolean judge(String str1, String str2) {
        if (str1 == null || str2 == null || str2.length() < 1 || str1.length() < str2.length()) {
            return false;
        }
        char[] a = str1.toCharArray();
        char[] b = str2.toCharArray();
        int i = 0;
        int j = 0;
        int[] next = getNextArray(b);
        while (i < a.length && j < b.length) {
            if (a[i] == b[j]) {
                i++;
                j++;
            } else if (next[j] == -1) {
                i++;
            } else {
                j = next[j];
            }
        }
        return j == b.length;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.right = new Node(5);
        head.left.right.right = new Node(6);

        Node head1 = new Node(5);
        head1.right = new Node(6);

        String str1 = serialize(head);
        System.out.println(str1);
        String str2 = serialize(head1);
        System.out.println(str2);
        boolean flag = judge(str1, str2);
        System.out.println(flag);
    }
}
